//
// Created by PC on 2024/2/22.
//


#include <iostream>
#include <vector>
#include "arrUtil.h"

using namespace std;

int part(vector<int> &v, int l, int r);
void sort(vector<int> &v, int l, int r);

int main()
{
    vector<int> arr = {7, 2, 9, 3, 6, 3, 6, 5, 4};
//    cout<<part(arr,0,arr.size()-1)<<endl;
    randVector(arr,1000);
    sort(arr,0,arr.size());
//    printVector(arr);
    cout<<checkSortVector(arr);
    return 0;
}


void sort(vector<int> &v, int l, int r)
{
    if(l<r)
    {
        int mid = part(v,l,r);
        sort(v,l,mid-1);
        sort(v,mid+1,r);
    }
}
// 分成小于等于区和大于区 以第一个数为基准
int part(vector<int> &v, int l, int r)
{
    int le = l - 1, cur = v[l];
    for (int i = l; i <= r; ++i)
    {
        if(v[i]<=cur)
        {
            le++;
            swap(v[le],v[i]);
        }
    }
    swap(v[le],v[l]);
    return le;
}
